// @algorithm @lc id=100300 lang=cpp
// @title fu-za-lian-biao-de-fu-zhi-lcof

#include "algm/algm.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution {
public:
    Node *copyRandomList(Node *head) {
        if (head == nullptr) {
            return nullptr;
        }
        Node *ptr = head;
        while (ptr != nullptr) {
            Node *temp = new Node(ptr->val);
            temp->next = ptr->next;
            ptr->next = temp;
            ptr = temp->next;
        }
        ptr = head;
        while (ptr != nullptr) {
            if (ptr->random) {
                ptr->next->random = ptr->random->next;
            }
            ptr = ptr->next->next;
        }
        Node *newHead = head->next;
        Node *slow = head;
        Node *fast = newHead;
        while (fast->next) {
            slow->next = fast->next;
            slow = slow->next;
            fast->next = slow->next;
            fast = fast->next;
        }
        slow->next = nullptr;
        return newHead;
    }
};